package com.c2b.algorithm.leetcode.base;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href='https://leetcode.cn/problems/reconstruct-original-digits-from-english/'>从英文中重建数字(Reconstruct Original Digits from English)</a>
 * <p>给你一个字符串 s ，其中包含字母顺序打乱的用英文单词表示的若干数字（0-9）。按 升序 返回原始的数字。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：s = "owoztneoer"
 *      输出："012"
 *
 * 示例 2：
 *      输入：s = "fviefuro"
 *      输出："45"
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>1 <= s.length <= 10^5</li>
 *         <li>s[i] 为 ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"] 这些字符之一</li>
 *         <li>s 保证是一个符合题目要求的字符串</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/12/15 14:37
 */
public class LC0423ReconstructOriginalDigitsFromEnglish_M {
    static class Solution {
        public String originalDigits(String s) {
            Map<Character, Integer> map = new HashMap<>();
            for (char c : s.toCharArray()) {
                map.put(c, map.getOrDefault(c, 0) + 1);
            }
            /*
            统计每个字母分别在哪些数字中出现：
                e ：0 1 3 5 7 8 9
                f ：4 5
                g ：8
                h ：3 8
                i ：5 6 8 9
                n ：1 7 9
                o ：0 1 2 4
                r ：0 3 4
                s ：6 7
                t ：2 3 8
                u ：4
                v ：5 7
                w ：2
                x ：6
                z ：0

             可以发现，z, w, u, x, g 都只在一个数字中，即 0,2,4,6,8 中出现。
             因此我们可以使用一个哈希表统计每个字母出现的次数，那么 z, w, u, x, g 出现的次数，即分别为 0,2,4,6,8 出现的次数。

             随后我们可以注意那些只在两个数字中出现的字符：
                h 只在 3,8中出现。由于我们已经知道了 8 出现的次数，因此可以计算出 3 出现的次数。
                f 只在 4,5中出现。由于我们已经知道了 4 出现的次数，因此可以计算出 5 出现的次数。
                s 只在 6,7中出现。由于我们已经知道了 6 出现的次数，因此可以计算出 7 出现的次数。

             此时，我们还剩下 1 和 9 的出现次数没有求出：
                o 只在 0,1,2,4 中出现，由于我们已经知道了 0,2,4 出现的次数，因此可以计算出 1 出现的次数。

             最后的 9 就可以通过 n, i, e 中的任一字符计算得到了。这里推荐使用 i 进行计算，因为 n 在 9 中出现了 2 次，e 在 3 中出现了 2 次，容易在计算中遗漏。

             当我们统计完每个数字出现的次数后，我们按照升序将它们进行拼接即可。
             */


            int[] cntArr = new int[10];
            cntArr[0] = map.getOrDefault('z', 0);
            cntArr[2] = map.getOrDefault('w', 0);
            cntArr[4] = map.getOrDefault('u', 0);
            cntArr[6] = map.getOrDefault('x', 0);
            cntArr[8] = map.getOrDefault('g', 0);

            cntArr[3] = map.getOrDefault('h', 0) - cntArr[8];
            cntArr[5] = map.getOrDefault('f', 0) - cntArr[4];
            cntArr[7] = map.getOrDefault('s', 0) - cntArr[6];

            cntArr[1] = map.getOrDefault('o', 0) - cntArr[0] - cntArr[2] - cntArr[4];
            cntArr[9] = map.getOrDefault('i', 0) - cntArr[5] - cntArr[6] - cntArr[8];

            StringBuilder stringBuilder = new StringBuilder();
            for (int i = 0; i < cntArr.length; i++) {
                for (int j = 0; j < cntArr[i]; j++) {
                    stringBuilder.append(i);
                }
            }
            return stringBuilder.toString();
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.originalDigits("owoztneoer"));
        System.out.println(solution.originalDigits("fviefuro"));
        System.out.println(solution.originalDigits("zeroonetwothreefourfivesixseveneightnine"));
    }
}
